package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.TreeNode;

import java.util.Stack;

/**
 * 判断一棵树是否是搜索二叉树
 *
 * @author Mr_wenpan@163.com 2021/12/20 21:16
 */
public class IsBst {

    public static void main(String[] args) {

    }

    public static boolean isBst(TreeNode<Integer> head) {
        if (head == null) {
            return true;
        }
        // 问左右子树要结果(后序遍历)
        boolean leftResult = isBst(head.left);
        boolean rightResult = isBst(head.right);

        boolean curResult = true;
        if (head.left != null) {
            curResult = head.data > head.left.data;
        }
        if (head.right != null) {
            curResult = head.data < head.right.data;
        }
        // 向上返回当前节点的结果
        return leftResult && rightResult && curResult;
    }

    public static boolean isBst2(TreeNode<Integer> head) {
        if (head == null) {
            return true;
        }

        boolean result = true;
        // 从头节点开始先序遍历（也可以后序遍历）
        if (head.left != null) {
            result = head.data > head.left.data;
        }
        if (head.right != null) {
            result = head.data > head.right.data;
        }
        // 一旦发现当前节点已经不是二叉搜索树了，则直接返回false。否则递归他的左右子树
        if (!result) {
            return false;
        }
        boolean leftResult = isBst2(head.left);
        boolean rightResult = isBst2(head.right);

        return leftResult && rightResult;
    }

    public static boolean isBst3(TreeNode<Integer> head) {
        if (head == null) {
            return true;
        }
        // 非递归写法(先序)
        Stack<TreeNode<Integer>> stack = new Stack<>();
        stack.push(head);
        boolean result = true;

        while (!stack.isEmpty()) {
            TreeNode<Integer> pop = stack.pop();
            // 先压右再压左
            if (pop.right != null) {
                stack.push(pop.right);
                result = pop.data < pop.right.data;
            }
            if (pop.left != null) {
                stack.push(pop.left);
                result = pop.data > pop.left.data;
            }
            // 一旦有某个节点不满足二叉搜索树条件，则直接返回
            if (!result) {
                return false;
            }
        }

        return true;
    }

    /**
     * 非递归实现中序遍历（核心思想：任何一棵树都能被左边界分解）
     */
    private static void inOrder(TreeNode<Integer> head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack = new Stack<>();
        TreeNode<Integer> cur = head;

        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                // 弹出一个节点，并且对他的有孩子也同样将左边界压栈
                cur = stack.pop().right;
                System.out.print(cur.data + "   ");
            }
        }

    }

    /**
     * 非递归实现后序遍历（核心思想：和先序遍历很类似）
     */
    private static void postOrder(TreeNode<Integer> head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack1 = new Stack<>();
        Stack<TreeNode<Integer>> stack2 = new Stack<>();

        // 先序遍历
        stack1.push(head);
        while (!stack1.isEmpty()) {
            // 弹出先不打印，而是暂存到另一个栈中
            TreeNode<Integer> pop = stack1.pop();
            stack2.push(pop);
            // 对于左右节点，先压左再压右（和先序遍历相反）
            if (pop.left != null) {
                stack1.push(pop.left);
            }
            if (pop.right != null) {
                stack1.push(pop.right);
            }
        }

        // 最后将结果倒出来就是后续遍历
        while (!stack2.isEmpty()) {
            TreeNode<Integer> pop = stack2.pop();
            System.out.print(pop.data + "   ");
        }

    }

}
